package com.leetcode.algorithm.y22.m06;

/**
 * 1539. 第 k 个缺失的正整数
 * 
 * https://leetcode.cn/problems/kth-missing-positive-number/
 * 
 * @author jie.deng
 *
 */
class Question1539Solution01 {
	
	public int findKthPositive(int[] arr, int k) {
		int left = 0;
		int right = arr.length;
		// 找第一个满足 arr[i] > i+k 的索引，可能最后一个也不满足
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] > k + mid) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return k + left;
	}
    
}